/*
 * @Description: Be careful what you wish for
 * @Autor: zzzzzed
 * @Date: 2023-11-28 01:05:54
 * @LastEditors: zzzzzed
 */

// 给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

// 你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。

// 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

// 文本的最后一行应为左对齐，且单词之间不插入额外的空格。

// 注意:

// 单词是指由非空格字符组成的字符序列。
// 每个单词的长度大于 0，小于等于 maxWidth。
// 输入单词数组 words 至少包含一个单词。


// 示例 1:

// 输入: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
// 输出:
// [
//    "This    is    an",
//    "example  of text",
//    "justification.  "
// ]
// 示例 2:

// 输入:words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
// 输出:
// [
//   "What   must   be",
//   "acknowledgment  ",
//   "shall be        "
// ]
// 解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
//      因为最后一行应为左对齐，而不是左右两端对齐。       
//      第二行同样为左对齐，这是因为这行只包含一个单词。
// 示例 3:

// 输入:words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"]，maxWidth = 20
// 输出:
// [
//   "Science  is  what we",
//   "understand      well",
//   "enough to explain to",
//   "a  computer.  Art is",
//   "everything  else  we",
//   "do                  "
// ]


/**
 * 分析
 * 1. 当前行是最后一行： 单词左对齐， 单词间有且只有一个空格， 在末尾填充剩余空格；
 * 2. 当前行不是最后一行且单词个数是1： 单词左对齐，在末尾填充剩余空格；
 * 3. 当前行不是最后一行且单词个数大于1： 设单词个数为numWords， 空格数为numSpaces
 *    avgSpaces = Math.floor(numSpaces/(numWords-1)),
 *    剩余空格extraSpaces = numSpaces % (numWords-1),前 extraSpaces 个单词之间填充 avgSpaces+1 个空格，其余单词之间填充 avgSpaces 个空格

 */

function fullJustify(words: string[], maxWidth: number): string[] {
    let res = [];
    let right = 0, n = words.length;
    while (true) {
        const left = right;
        let sumStr = 0;
        console.log(" right = ", right, " === sumStr = ", sumStr);
        while (right < n && sumStr + words[right].length + (right - left) <= maxWidth) {
            sumStr += words[right].length;
            right++;
        }
        // 当前行是最后一行
        if (right === n) {
            let s = words.slice(left).join(" ");
            res.push(s + blank(maxWidth - s.length));
            break;
        }
        let numWords = right - left;
        let numSpaces = maxWidth - sumStr;
        if (numWords == 1) {
            let s = words[left];
            res.push(s + blank(numSpaces));
            continue;
        }
        let avgSpaces = Math.floor(numSpaces / (numWords - 1));
        let extraSpaces = numSpaces % (numWords - 1);
        const s1 = words.slice(left, left + extraSpaces + 1).join(blank(avgSpaces + 1));
        const s2 = words.slice(left + extraSpaces + 1, right).join(blank(avgSpaces));
        res.push(s1 + blank(avgSpaces) + s2);
    }
    return res;

};

// 空格填充
function blank(n: number): string {
    return new Array(n).fill(" ").join("");
}

let words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16;

let res = fullJustify(words, maxWidth);
console.log(res);